package binaryTree;

import java.util.HashMap;
import java.util.Map;

/*
 *@description 添加与搜索单词 - 数据结构设计
 *@author hkfan
 *@version 1.0
 *@create 2025/6/24 10:28
 */
public class LeetCode_211 {
    class WordDictionary {

        class Node{
            char val;
            int end=0;
            Map<Character,Node> map;

            public Node(char val) {
                this.val = val;
                this.end = 0;
                this.map = new HashMap<>();
            }
        }
        Node root;

        public WordDictionary() {
            root=new Node('0');
        }

        public void addWord(String word) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                if (!cur.map.containsKey(word.charAt(i))){
                    cur.map.put(word.charAt(i),new Node(word.charAt(i)));
                }
                cur=cur.map.get(word.charAt(i));
            }
            cur.end++;
        }

        public boolean search(String word) {
            return search(word,root,0);
        }

        public boolean search(String word,Node cur,int i){
            if (i==word.length()){
                return cur.end!=0;
            }
            Boolean res = false;
            if (word.charAt(i)=='.'){
                for (Node node : cur.map.values()) {
                    res=res||search(word,node,i+1);
                }
            }else {
                if(cur.map.containsKey(word.charAt(i))){
                    res = res || search(word,cur.map.get(word.charAt(i)),i+1);
                }else {
                    return false;
                }
            }
            return res;
        }
    }
}
